package com.logbug.algorithm;

import java.util.Arrays;

public class Test2 {
    public static void main(String[] args) {
        int[] arr = new int[]{1, 3, 2, 5, 3, 7, 5, 9};
        QuickSort sorter = new QuickSort(arr);
        sorter.sort();
        System.out.println(Arrays.toString(arr));
    }

    static class QuickSort {
        int[] arr;

        public QuickSort(int[] arr) {
            this.arr = arr;
        }

        void sort() {
            sort(0, arr.length - 1);
        }

        void sort(int left, int right) {
            if (left < right) {
                int c = left, index = left + 1;
                for (int i = index; i <= right; i++) {
                    if (arr[index] < arr[c]) {
                        swap(index++, i);
                    }
                }
                swap(--index, c);
                sort(left, index - 1);
                sort(index + 1, right);
            }
        }

        void swap(int i, int j) {
            int t = arr[i];
            arr[i] = arr[j];
            arr[j] = t;
        }
    }
}

